package HeapCreate;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-03-27
 * Time: 21:05
 */
public class Heap {
    public int[] elem;
    public int usedSize;

    public Heap() {
        this.elem = new int[10];
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    //大堆的创建
    public void createBigHeap() {
        //由最后一棵子树的结点找到它的父节点下标，然后从这棵子树开始向下调整，依次下标减1.
        for(int parent = (usedSize-1-1)/2;parent>=0;parent--) {
            //此刻传的两个参数，分别为要向下调整的根结点的下标和这个数组的长度
            //为什么传的数组的长度，因为这个向下调整是一个过程，它总有一个时间段是停下的，传的这个数组长度就是一个临界条件
            siftDown1(parent,usedSize);
        }
    }
    //向下调整的方法
    public void siftDown1(int p,int end) {
        //得到该结点的子结点的下标
        int c = 2*p + 1;
        //临界条件：子结点的下标<数组的长度
        while(c < end) {
            //找到最大的子结点
            if(c+1<end && elem[c] < elem[c+1]) {
                c++;
            }
            //将该结点与最大子结点比较，如小于则交换否则直接break返回
            if(elem[p] < elem[c]) {
                //交换
                swap(p,c);
                //将指向该结点的引用指向该结点的子结点，再重新将子结点的下标进行变化，检查该结点的子树是否满足大堆，不满足则继续向下调整
                p = c;
                c = 2*p + 1;
            } else {
                break;
            }
        }
    }
    //交换方法
    public void swap(int x, int y) {
        int tmp = elem[x];
        elem[x] = elem[y];
        elem[y] = tmp;
    }

    //小堆创建
    public void createSmallHeap() {
        //由最后一棵子树的结点找到它的父节点下标，然后从这棵子树开始向下调整，依次下标减1.
        for(int parent = (usedSize-1-1)/2;parent>=0;parent--) {
            //此刻传的两个参数，分别为要向下调整的根结点的下标和这个数组的长度
            //为什么传的数组的长度，因为这个向下调整是一个过程，它总有一个时间段是停下的，传的这个数组长度就是一个临界条件
            siftDown2(parent,usedSize);
        }
    }
    //向下调整的方法
    public void siftDown2(int p,int end) {
        //得到该结点的子结点的下标
        int c = 2*p + 1;
        //临界条件：子结点的下标<数组的长度
        while(c < end) {
            //找到最小的子结点
            if(c+1<end && elem[c] >elem[c+1]) {
                c++;
            }
            //将该结点与最小子结点比较，如大于则交换否则直接break返回
            if(elem[p] > elem[c]) {
                //交换
                swap(p,c);
                //将指向该结点的引用指向该结点的子结点，再重新将子结点的下标进行变化，检查该结点的子树是否满足大堆，不满足则继续向下调整
                p = c;
                c = 2*p + 1;
            } else {
                break;
            }
        }
    }

    //堆的删除(堆的删除一定是堆顶元素)
    public int poll() {
        //记录删除的元素
        int tmp = elem[0];
        //交换堆顶元素与最后一个元素
        swap(0,usedSize-1);
        //数组长度减1
        usedSize--;
        //对堆顶元素向下调整,因为这个堆本身之前是一个大堆，堆顶之下的结点基本都满足大堆的规则，所以只需要从堆顶的元素向下调整即可
        // 直到这个堆完全满足大堆的特性
        siftDown1(0,usedSize);
        return tmp;
    }

    //堆的插入
    public void offer(int val) {
        //1.判断是否扩容
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //插入元素
        elem[usedSize] = val;
        usedSize++;//11
        //向上调整
        siftUp(usedSize-1);

    }

    private void siftUp(int child) {
        int parent = (child-1)>>>1;   //>>>1等于除于2
        while(child > 0) {
            //判断child与parent的大小
            if(child >parent) {
                //交换
                swap(parent,child);
                //移动c与p的位置
                child = parent;
                parent = (child-1)>>>1;
            } else {
                break;
            }
        }
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }
    public void heapSort() {
        int end = usedSize-1;
        while(end>0) {
            swap(0,end);
            siftDown1(0,end-1);
            end--;
        }
    }
}
